#include <iostream>
#include <vector>
using namespace std;
/*伪计数排序
void CountingSort (vector<int>& v) {
	vector<int> counting(10,0);
	for(auto t : v) 
		counting[t - 1]++;
	int index = 0;
	for(int i = 0; i < counting.size(); i++) {
		while(counting[i]!=0) {
			v[index++] = i + 1;
			counting[i]--;
		}
	}
}*/
/*
区别就在于计数排序并不是把计数数组的下标直接作为结果输出,
而是通过计数的结果，计算出每个元素在排序完成后的位置，然后将元素赋值到对应位置。
计数排序的局限：只能用于特定的场景。在对一定范围内的整数排序时，它的时间复杂度为 O(n+k)，空间复杂度也是 O(n+k)。
*/

void CountingSort1 (vector<int> &v) {
	vector<int> counting(11,0);//十一为计数范围，0-10
	int len = counting.size();
	for(auto& t : v) {
		counting[t]++;
	}
	int prenum = 0;
	int t;
	for(int i = 0; i < len; i++) {
		t = counting[i];
		counting[i] = prenum;
		prenum += t;
	}
	vector<int> result{v};
	for(auto& t : v) {
		int index = counting[t];	
		result[index] = t;
		counting[t]++;
	}
	v = result;
}

//倒序的计数排序
void CountingSort2 (vector<int> &v) {
	int max = v[0];
	int min = v[0];
	for(auto& t : v) {
		if(t > max) max = t;
		else if(t < min) min = t;
	}
	int range = max - min + 1;
	vector<int> counting(range, 0);//0 ~ range-1 对应 min ~ max
	for(auto& t : v) {
		counting[t - min]++;
	}
	counting[0]--; 
	//每个元素在结果数组中的最后一个下标位置 = 前面比自己小的数字的总数 + 自己的数量 - 1
	for(int i = 1; i < range; i++)
	{
		counting[i] += counting[i-1];
	}
	vector<int> result{v};
	for(int i = v.size() - 1; i >= 0; i--) {
		int temp = counting[v[i] - min];
		result[temp--] = v[i];
		/*result[counting[v[i] - min]] = v[i];
		counting[v[i] - min]--;*/
	}
	v = result;
}



int main() {
	vector<int> v{1,4,3,2,7,9,5,0,4,10,6,3};
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	//CountingSort1(v);
	CountingSort2(v);
	
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	return 0;
}